#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class UnionFind
{
public:
    UnionFind(int N) : N(N)
    {
        parent = new int[N + 1];
        fill(parent, parent + N + 1, -1);
        size = new int[N + 1];
        fill(size, size + N + 1, 1);
    }
    int Find(int x)
    {
        if (parent[x] == -1)
            return x;
        int parx = Find(parent[x]);
        parent[x] = parx;
        return parx;
    }
    void Union(int x, int y)
    {
        int parx = Find(x), pary = Find(y);
        if (parx == pary)
            return;
        if (size[parx] < size[pary])
        {
            parent[parx] = pary;
            size[pary] += size[parx];
            size[parx] = 0;
        }
        else
        {
            parent[pary] = parx;
            size[parx] += size[pary];
            size[pary] = 0;
        }
    }
    bool isOneClass(int x, int y) { return Find(x) == Find(y); }
    int maxCluster()
    {
        int ret = -1;
        for (int i = 0; i < N; ++i)
        {
            ret = max(ret, size[i]);
        }
        return ret;
    }

private:
    int *parent, *size, N;
};
class Solution
{
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>> &edges)
    {
        UnionFind alice(n), bob(n);
        int cnt = 0, ret = 0;
        for (auto edge : edges)
        {
            int type = edge[0], x = edge[1], y = edge[2];
            switch (type)
            {
            case 3:
                if (alice.isOneClass(x, y) || bob.isOneClass(x, y))
                    ret += 1;
                alice.Union(x, y);
                bob.Union(x, y);
                break;
            default:
                break;
            }
            cnt++;
        }
        for (auto edge : edges)
        {
            int type = edge[0], x = edge[1], y = edge[2];
            switch (type)
            {
            case 1:
                if (alice.isOneClass(x, y))
                    ret += 1;
                alice.Union(x, y);
                break;
            case 2:
                if (bob.isOneClass(x, y))
                    ret += 1;
                bob.Union(x, y);
                break;
            default:
                break;
            }
            cnt++;
        }
        if (alice.maxCluster() < n || bob.maxCluster() < n)
            return -1;
        return ret;
    }
};